(Problem) 009 Special Pythagorean triplet

작성일 In 댓글:

Project Euler

  • 공식 홈페이지 - projecteuler.net
  • 한글 번역 - projecteuler @kr
  • (HackerRank) ProjectEuler+ - hackerrank.com

Problem

Special Pythagorean triplet


problem <번역>

solution

Simple Code

a, b, c를 하나 하나 대입하면서 조건을 만족하는 답을 찾는 매우 단순한 풀이
O(n²)의 성능을 가진다.

009_Even_Fibonacci_numbers.py
def special_pythagorean_triplet(n):
  # condition 1. a^2 + b^2 = c^2  (직삼각형)
  # condition 2. a + b + c = n    (문제에서 n은 1000)

  for a in range(1, n//2 + 1):
      for b in range(1, n//2 + 1):
          c = n - a - b
          if a**2 + b**2 == c**2:
              return a * b * c


print(special_pythagorean_triplet(1000))
HackerRank

예상대로 O(n²)의 복잡도로는 모든 테스트 케이스를 통과할 수 없다. 또한 항상 해가 하나만 있는 것은 아니다.
한 개의 반복문만 사용하기 위해서 b도 a로 표현한다.

정리하자면,
a = 1 ~ n//2 까지 대입
b = (a^2 - (a - n)^2) // 2(a-n) = n(2a-n) // 2(a-n)
c = n - a - b

009_for_HacerRank.py
def special_pythagorean_triplet(n):
    # condition 1. a^2 + b^2 = c^2  (직삼각형)
    # condition 2. a + b + c = n    (문제에서 n은 1000)

    maxProduct = -1
    for a in range(1, n//2 + 1):
        b = (n*(2*a - n)) // (2*a - 2*n)
        c = n - a - b
        if a**2 + b**2 == c**2:
            product = a * b * c
            maxProduct = product if product > maxProduct else maxProduct

    return maxProduct if maxProduct > 0 else -1


if __name__ == '__main__':
    for _ in range(int(input())):
        print(special_pythagorean_triplet(int(input())))

가장 기본적인 성능 개선 방법: 반복문을 줄인다!